package hot100.logos71To80;

import java.util.Stack;

/**
 * @author logos
 * date 2025/7/17 12:36
 * @version v1.0
 * @Package hot100.logos71To80
 */
public class logos73 {

    /**
     * 73. 柱状图中最大的矩形
     * https://leetcode.cn/problems/largest-rectangle-in-histogram/description/?envType=study-plan-v2&envId=top-100-liked
     */

    class Solution {
        public int largestRectangleArea(int[] heights) {
            int n = heights.length;
            int ans = 0;
            Stack<Integer> st = new Stack<>();
            for (int i = 0; i < heights.length; i++) {
                while (!st.isEmpty() && heights[i] <= heights[st.peek()]) {
                    int cur = st.pop();
                    int left = !st.isEmpty() ? st.peek() : -1;
                    ans = Math.max(ans, (i - left - 1) * heights[cur]);
                }
                st.push(i);
            }
            while (!st.isEmpty()) {
                int cur = st.pop();
                int left = !st.isEmpty() ? st.peek() : -1;
                ans = Math.max(ans, (n - left - 1) * heights[cur]);
            }
            return ans;
        }
    }
}
